#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <sstream>
using namespace std;

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//序列化二叉树，递归前序遍历，leetcode-297
class Solution
{
public:
    string helpSerialize(TreeNode *root)
    {
        if (!root)
        {
            return "#";
        }
        return to_string(root->val) + " " + helpSerialize(root->left) + " " + helpSerialize(root->right);
    }
    char *Serialize(TreeNode *root)
    {
        if (!root)
        {
            return nullptr;
        }
        string s;
        s = helpSerialize(root);
        char *res = new char[s.size()];
        strcpy(res, s.c_str());
        return res;
    }
    TreeNode *helpDeserialize(istringstream &in)
    {
        string val;
        in >> val;
        if (val == "#")
            return nullptr;
        auto root = new TreeNode(stoi(val));
        root->left = helpDeserialize(in);
        root->right = helpDeserialize(in);
        return root;
    }
    TreeNode *Deserialize(char *str)
    {
        if (!str)
        {
            return nullptr;
        }
        string s = str;
        istringstream in(s);
        return helpDeserialize(in);
    }
};

void test()
{
}

int main()
{
    test();
    return 0;
}